A content addressable memory (CAM) is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data in the comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., random access memory (RAM), dynamic RAM (DRAM), etc.). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads into or gets back the data at the specified address.
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address bus, or the data can be written into the first empty memory location. Every location has a pair of status bits that keep track of whether the location is storing valid information in it or is empty and available for writing.
Once information is stored in a memory location, it is found by comparing every bit in memory with data in the comparand register. When the content stored in the CAM memory location does not match the data in the comparand register, the local match detection circuit returns a no match indication. When the content stored in the CAM memory location matches the data in the comparand register, a local match detection circuit returns a match indication. If one or more local match detection circuits return a match indication, the CAM device returns a “match” indication. Otherwise, the CAM device returns a “no-match” indication. In addition, the CAM may return the identification of the address location in which the matched data is stored or one of such addresses if more than one address contained matching data. Thus, with a CAM, the user supplies the data and gets back the address if there is a match found in memory.
Locally, CAMs may perform match detection using an exclusive-NOR (XNOR) function, so that a match is indicated only if both the stored bit and the corresponding input bit are the same state. CAMs are designed so that any number of stored bits may be simultaneously detected for a match with the input bits in the match detection circuit. One way in which this is achieved is by coupling a plurality of storage devices and logic circuits to a common matchline, as depicted in FIG. 1.
Turning to FIG. 1, a schematic diagram of a conventional match detection circuit 100 is depicted. A first source/drain terminal of a precharge transistor 102 is coupled to a positive voltage source (e.g., VDD). The gate of transistor 102 is coupled to a signal line 138 for receiving a precharge signal. A second source/drain terminal of transistor 102 is coupled to a matchline 140 for precharging the matchline 140 to a predetermined voltage level (e.g., VDD).
The match detection circuit 100 includes several CAM cells 191, which are used to store data. CAM cells 191 also compare the stored data to comparand data to determine if the stored data and the comparand data are substantially the same. Each CAM cell 191 is coupled to matchline 140 through lines 120, 122. Each CAM cell 191 is coupled to discharge line 142 through lines 128, 130. The discharge line 142 is electrically coupled to a ground potential through line 190.
Also coupled to the matchline 140 is a buffer 136 for buffering the matchline 140 voltage and for outputting a match signal. Typically, a logic high (e.g., VDD) match signal indicates that an exact match was detected between the input comparand bits and the stored bits. A logic low (e.g., Ground) match signal represents that at least one bit of the stored data did not match its corresponding input bit.
FIG. 2 shows a portion of the FIG. 1 circuit in greater detail. The CAM cell 191 of FIG. 2 is representational of any of the CAM cells 191 of FIG. 1. The CAM cell 191 includes a storage element 104 and transistors 110, 112, 106, 108, 162, 164. The storage element 104 is used to store a data bit and the complement of the data bit. The output Q0 of storage element 104, which is to be compared with the complement input bit B0*, is coupled to the gate of transistor 106. The first source/drain terminal of transistor 106 is coupled to the matchline 140 (FIG. 1) through line 120. The second source/drain terminal of transistor 106 is coupled to transistor 110. The second source/drain terminal of transistor 110 is coupled to discharge line 142 (FIG. 1) through line 128. The gate of transistor 110 is coupled to complement input bit B0*.
Input bit B0, used to store information in the storage element, is also coupled to the first source/drain terminal of transistor 162 through line 150. The second source/drain terminal of transistor 162 is coupled to an input of storage element 104. The gate of transistor 162 is coupled to wordline 144.
Further, the complement output Q0* of storage element 104, which is to be compared with the input bit B0, is coupled to the gate of transistor 108. First source/drain terminal of transistor 108 is coupled to the matchline 140 (FIG. 1) through line 122. The second source/drain terminal of transistor 108 is coupled to transistor 112. The second source/drain terminal of transistor 112 is coupled to discharge line 142 (FIG. 1) through line 130. The gate of transistor 112 is coupled to the input bit B0.
Complement input bit B0* is also coupled to the first source/drain terminal of transistors 164 through line 152. The second source/drain terminal of transistor 164 is coupled to an input of storage element 104. The gate of transistor 164 is coupled to a wordline 144.
To write to or to read from the storage element 104, the wordline 144 is set to a logic high then to a logic low, which temporarily activates transistors 162, 164 and couples the storage element 104, to input bit B0 and the complement input bit B0*.
Referring to FIGS. 1 and 2, during operation of the match detection circuit 100, the precharge signal goes logic low then logic high in order to precharge the matchline 140 to VDD. The states of a bit stored by storage element 104 and the complement of the stored bit are respectively coupled to the gates of transistors 106, 108 via outputs Q0, Q0*. Consequently, depending upon the states at their respective gates, the transistors 106, 108 may become active.
Similarly, the states of the input bit B0 and its complement B0* are coupled to the gates of transistors 112, 110. Consequently, depending upon the states at their respective gates, the transistors 112, 110 may be active. Consequently, input bit B0 and its complement B0* serve two functions: they function to read and write information to the storage element 104 and they also function to carry the information stored in the comparand for comparison with information stored in the storage element 104.
As seen in FIG. 2, when a match is detected, at least one transistor of each serially connected pair of transistors (e.g., 106 and 110, 108 and 112) is inactive and not conducting. Therefore, when the matchline 140 remains logic high, this signifies to the outside world that a match has been detected and potentially enables any other functions desired when a match is detected (e.g., provide the user with the address of the memory location where the match was found, forward the data to another location, etc.).
However, when a mismatch is detected, as is most often the case during a search for a particular bit pattern, at least one pair of serially connected transistors (e.g., 106 and 108, 110 and 112) is active and conducting and the matchline 140 is coupled to the ground potential. When the matchline 140 is coupled to the ground potential, the match signal goes logic low, which signifies to the outside world that a mismatch has been detected for this storage element 104. Although match circuit 100 of FIG. 1 is shown with two CAM cells 191, any number of CAM cells may be utilized.
In the above-identified search process, the searched data (i.e., the input bits from the comparand) is simultaneously compared with every data word in the match detection circuit 100 in order to find a match between the stored data and the input data.
Conventional testing of the match detection circuit 100 begins by precharging the matchline 140 to a predetermined voltage, e.g., VDD, so that the matchline 140 floats (assuming no significant leakage otherwise exists in the circuit). Stored data in the match detection circuit 100 is then compared to comparand data. Using predetermined comparand and stored data, the expected results (e.g., match or mismatch) are easily determined. The actual results of the test are compared with the expected results to determine the reliability of the match detection circuit 100.
Because of the architecture of the match detection circuit 100, it is possible that, due to defects during design or manufacturing, the circuits within the match detection circuit 100 will cause an erroneous match or mismatch signal to be generated. Further, elements of an array containing match detection circuits 100 may pass conventional tests, but they may be “weak” or marginally acceptable.
Therefore, it is desirable to test the margin of the match detection circuit 100 to determine its reliability.